package 二叉树;

import com.alibaba.fastjson.JSON;
import com.sun.jmx.remote.internal.ArrayQueue;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

public class NC60判断一棵树是否为二叉搜索树和完全二叉树 {

    /**
     * 给定一棵二叉树，已经其中没有重复值的节点，请判断该二叉树是否为搜索二叉树和完全二叉树。
     */

    public boolean[] judgeIt (TreeNode root) {
        return new boolean[]{validBinarySearchTree(root),judgeCompletelyTree(root)};
    }

    private boolean validBinarySearchTree(TreeNode root) {
        return validBinarySearchTree(root,Integer.MAX_VALUE,Integer.MIN_VALUE);
    }

    private boolean validBinarySearchTree(TreeNode node,Integer maxNum,Integer minNum) {
        if(node==null){
            return true;
        }
        if(node.val>=maxNum||node.val<=minNum){
            return false;
        }
        return validBinarySearchTree(node.left,node.val,minNum)
                &&validBinarySearchTree(node.right,maxNum,node.val);
    }

    /**
     * 完全二叉树的验证应该采用层序遍历,当层序遍历遇到null值时,此时null值后面还有节点,就为非完全二叉树
     */
    private boolean isCompleteTree(TreeNode root) {

        //注意: ArrayDeque 不支持 null元素
        LinkedList<TreeNode> queue=new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()){
            TreeNode treeNode = queue.removeFirst();
            if(treeNode==null){
                break;
            }
            queue.addLast(treeNode.left);
            queue.addLast(treeNode.right);
        }

        while (!queue.isEmpty()){
            if(queue.pollFirst()!=null){
                return false;
            }
        }
        return true;
    }


    //不是很好的方法
    private boolean judgeCompletelyTree(TreeNode root) {
        int leftMaxDeep = getLeftMaxDeep(root, 0);
        return dfsDeep(root,0,leftMaxDeep);
    }

    private int getLeftMaxDeep(TreeNode node,int deep) {
        if(node==null){
            return deep;
        }
        return getLeftMaxDeep(node.left,deep+1);
    }

    private boolean isDuan;

    private boolean dfsDeep(TreeNode node,int deep,int maxDeep) {
        if(node==null){
            if(deep>maxDeep){
                return false;
            }
            if(deep<maxDeep-1){
                return false;
            }
            if(deep==maxDeep-1){
                isDuan=true;
            }
            if(isDuan&&deep!=maxDeep-1){
                return false;
            }
            return true;
        }
        return dfsDeep(node.left,deep+1,maxDeep)&&dfsDeep(node.right,deep+1,maxDeep);
    }

    public static void main(String[] args) {
        NC60判断一棵树是否为二叉搜索树和完全二叉树 n=new NC60判断一棵树是否为二叉搜索树和完全二叉树();
        TreeNode treeNode = TreeNode.getNodeByArr(new Integer[]{8});
        boolean[] booleans = n.judgeIt(treeNode);
        System.out.println(JSON.toJSONString(booleans));
    }

}
